package com.zklh.leetcode.top100;

import java.util.*;

/**
 * 划分字母区间算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/10/11
 */
public class Solution763 {
    public List<Integer> partitionLabels(String s) {
        Map<Character, Integer> charToCount = new HashMap<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            charToCount.put(s.charAt(i), 1+charToCount.getOrDefault(s.charAt(i), 0));
        }
        int balance = 0;
        int current = 0;
        int start = 0;
        Set<Character> traceChars = new HashSet<>();
        while (current < s.length()) {
            start = current;
            do {
                if (traceChars.contains(s.charAt(current))) {
                    balance--;
                } else {
                    balance += charToCount.get(s.charAt(current))-1;
                    traceChars.add(s.charAt(current));
                }
                current++;
            } while (balance > 0);
            result.add(current - start);
            traceChars.clear();
        }
        return result;
    }

    public static void main(String[] args) {
        Solution763 solution763 = new Solution763();
        // String s = "ababcbacadefegdehijhklij";
        String s = "eccbbbbdec";
        System.out.println(solution763.partitionLabels(s));
    }
}